package sword2offer;

/**
 * <p>
 * 反转链表
 * </p>
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * @author LovelyBigDuck
 * @date 2022/3/14 20:24
 */

/**
 * 思路一：临时存放前一个节点，遍历更改指针指向
 * 思路二：递归
 * 思路三：栈
 */
public class S_24 {
     public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
     }

    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev=null;
            ListNode curr=head;
            while(curr!=null){
                ListNode next=curr.next;
                curr.next=prev;
                prev=curr;
                curr=next;
            }
            return prev;
        }

        public ListNode reverseList1(ListNode head) {
            if(head==null||head.next==null){
                return head;
            }
            ListNode newHead=reverseList1(head.next);
            head.next.next=head;
            head.next=null;
            return newHead;
        }
    }
}
